Computers normally include an arithmetic logic unit that includes an adder that adds numbers of some maximum number of bits. Adders for words of length 32 and 64 bits are common in microprocessors and the like. While these adders will also operate on much smaller words, when doing so, the majority of the logic circuits contained in the adders are idle. For example, a 64-bit adder can be used to add two 8-bit words by placing each of the 8-bit words in the least significant portion of a corresponding 64-bit word and then adding the 64-bit words. During the addition, the logic circuitry concerned with adding the 7 high order bytes of each of the words is effectively idle. Hence, 7/8.sup.ths of the capacity of the adder is being wasted during this operation.
Computations involving the addition of a large number of pairs of small words are often encountered in multi-media data processing. For example, consider the problem of adding two gray-scale images to generate a sum image. The pixels of the images are typically stored as one byte integers representing the light intensity at a corresponding point in the image. Since storage space is always at a premium, the pixels of the image are typically packed into words. If the basic word size on the computer is 32-bits, the pixels could be packed four per word. Each image may have a million pixels. Hence, the computation of the sum image involves adding two pixels from the component image to generate a corresponding pixel in the sum image. If there are a million pixels in each image, a million such additions must be performed. Each addition requires the "unpacking" of two words, one from each component image, the addition of the two unpacked bytes, and then the storage of the result in the correct byte of a word in the sum image.
If the basic word size of the computer is 32-bits, the computer will normally have a 32-bit adder. During these computations, 75% of the adding capacity of the adder will be idle. Hence, a conventional arithmetic logic unit is not being used optimally when performing this type of image calculation.
The computation times encountered in these types of operations can be excessive. Hence, special parallel computer architectures are often employed to reduce the time between the execution of the sum image command and the time at which the sum image is completed. Since all of the additions are independent of each other, the adds can be performed in parallel without regard to ordering. A computer with M adders can, in principle, provide a result in 1/M.sup.th the time provided the movement of the pixels from memory to the adders does not become a bottleneck. Hence, it would be advantageous to provide a computer architecture in which multiple additions can be performed in parallel. Unfortunately, the cost of providing these additional adders and the hardware needed to control them is often prohibitive.
It should also be noted that the image addition problem discussed above often includes generating an average image. An image having pixels that are the average of the corresponding pixels in the component images is equivalent to generating the pixels of the sum image discussed above and then dividing the intensity of each of the sum image pixels by 2. This type of image computation is preferred since it prevents overflows. If the two corresponding component image pixel values have values greater than 128, then the sum image pixel cannot be represented as an 8-bit integer. To avoid this problem, the average image is used, since the average image pixels will always be representable as one byte integers if the component image pixels were one byte integers.
Broadly, it is the object of the present invention to provide an improved adder.
It is a further object of the present invention to provide an adder that operates at high efficiency when multiple additions involving words that are smaller than the width of the adder are added.
It is yet another object of the present invention to provide an adder that can generate the average of two numbers in a single machine cycle.
It is a still further object of the present invention to provide an adder that is adapted for computing a plurality of average values of pairs of numbers that are smaller than the width of the adder.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.